Many people store multimedia files, such as music, on their computers in MP3 or WMA format or the like. These files can be played in any order selected from the entire collection. These multimedia files may be played on the computer, DVD players, car stereos, and other portable players such as specialized MP3 players.
Typically, it is desirable to make a playlist that is basically a list that defines which multimedia files (e.g. songs) to play in which order. Such a list can be created manually by adding songs to the playlist one by one. However, this is a very tedious, especially if the collection of music files is extensive. A much simpler way to create a playlist is to let the player randomly play songs from the entire, or a part of the, music collection. However, usually playlists are created with a special purpose in mind, for example to listen to while relaxing or while driving the car etc. In these cases, the listener, invariably, wants to be able to specify more precisely what type of music is played. Therefore, it is desirable that the music player generates a playlist automatically, or at least assists the listener in doing so, in accordance with the listener's specific desires.
There are several known types of automatic playlist generators. One known system learns the user's preference for songs and subsequently generates a set of songs that the system thinks the user would enjoy. In determining which songs the user would like there are two different approaches: content-based learning and collaborative filtering. Content-based learning looks at the songs themselves and at the attributes of those songs in particular and matches songs that are similar according to their attributes. The idea is that if a user likes a particular song, the user will also like a song that is similar to it. The input from the user for these systems usually consists of one or more seed song and the system then outputs a set of songs that are similar to the seed song(s). Because the song order is not taken into account and the user cannot specify other constraints than that the songs in the list should be similar to the seed song, this system has very limited use.
Collaborative filtering is a multi-user approach that utilizes explicit preferences to match songs to a specific user. Each user expresses their preferences for a set of songs. The system then tries to expand this set of preferred songs by finding users that have a similar taste in music and recommending the songs that these users have indicated to like. The playlists that are generated by this system are actually playsets since the song order is not taken into account or is considered a matter of minor importance and again the system has limited use.
The main objective of the above systems is to introduce new music to the users; they do not offer the user assistance in creating a specific playlist for a specific situation.
Another known method is to provide a solution playlist on the basis of constraints defined by the user that have to be satisfied, and operated in a network. Each node in the network represents a song, costs and weights to represent the constraints that have to be satisfied. The object is to find a continuous path connecting the source and the sink (the first and the last song in the playlist, respectively, which could be dummy songs) that has a minimum cost and at the same time has constrained weights. In the model, songs are represented as vectors of binary values, which limits the attributes and hence constraints that can be defined
Another known playlist generator uses a constraint satisfaction programming (CSP) method. CSP associates a constrained variable with each position in the playlist, where the domain of each of the variables is the music collection. The idea is to assign a value from the domain to each of the variables, which corresponds to a sequence of songs. However, the number of songs in the playlist is fixed by defining the variables in the CSP, and therefore does not allow the user to define the duration of the playlist they desire for example. The algorithm, which searches for a solution, consists of reducing each domain one after the other, until it either leads to a solution or fails to find one. Every time a value is removed from a domain, the constraints acting on this domain are inspected to check if any constraint implies that another value, belonging to another domain, becomes forbidden. If so, it is removed too, and the process is repeated recursively (constraint propagation). Domain reduction then occurs either by choice (assigning a value to a variable), or as consequence of the propagation required for the satisfaction of some constraints. Upon failure (a domain becomes empty), the algorithm backtracks to the last decision that was made, takes a different one, and tries again. If there's no solution either, the algorithm backtracks one step further, and examines the stack of decisions bottom to top until it can either prove that there's no solution, or find one. So the solution playlist is constructed by repeatedly adding songs to the playlist and testing if the playlist can still be completed. Therefore, only a partial playlist is available at each iteration, which may be problematical if the algorithm is stopped prematurely. This CSP algorithm is, therefore, complex and as a result has limited scalability. Further, the CSP algorithm does not incorporate a notion of optimality which is desirable for playlist generation.
Another known technique for automatic playlist generation is a local search method. The method starts with a random list of songs and iteratively tries to improve upon this playlist by making small changes such as (i) adding a song, (ii) deleting a song, (iii) replacing a song by a new one, and (iv) swapping two songs in the playlist. To achieve this a cost is associated with the playlist and the more constraints that are violated (not satisfied) by the playlist and the larger that violation, the higher the cost. The local search is an iterative process in which, at each iteration, the resulting playlist of the previous and current iterations are compared and the resulting playlist with the lower cost becomes the result of the current iteration. Therefore, at any time, there is a complete solution playlist, and it is possible to stop the algorithm at any time to return the best playlist found so far, i.e. the latest result. The algorithm does not investigate all possible playlists but progressively refines solutions and consequently has a better scalability and incorporates optimality.
However, if a particular constraint is hard to satisfy, randomly generating a new solution (making a small random change) and checking whether the violation has decreased, is likely to lead to rejection of the current solution and the search algorithm will make very little progress and will become extremely slow.
An example of constraints that are hard to satisfy by randomly changing the original solution is the constraint that we want to have three songs of a certain artist, when the current solution has two. Replacing a song by a random other song will then have a very low probability of being of the right artist, and hence the new solution will most likely also not have three songs of this artist.